#include <iostream>
#include <vector>
using namespace std;

//class Solution {
//public:
//    int peakIndexInMountainArray(vector<int>& arr) {
//        int left = 0;
//        int right = arr.size() - 2;
//        while (left < right)
//        {
//            int mid = (left + right) / 2;
//            if (arr[mid + 1] > arr[mid])
//            {
//                left = mid + 1;
//            }
//            else
//            {
//                right = mid;
//            }
//        }
//        return left;
//    }
//};
//
//class Solution {
//public:
//    int peakIndexInMountainArray(vector<int>& arr) {
//        int left = 0;
//        int right = arr.size() - 2;
//        while (left < right)
//        {
//            int mid = (left + right + 1) / 2;
//            if (arr[mid - 1] < arr[mid])
//            {
//                left = mid;
//            }
//            else
//            {
//                right = mid - 1;
//            }
//        }
//        return left;
//    }
//};
//
//class Solution {
//public:
//    int findPeakElement(vector<int>& nums) {
//        int left = 0;
//        int right = nums.size() - 1;
//        while (left < right)
//        {
//            int mid = (left + right) / 2;
//            if (nums[mid] > nums[mid + 1])
//            {
//                right = mid;
//            }
//            else
//            {
//                left = mid + 1;
//            }
//        }
//        return left;
//    }
//};
//
//class Solution {
//public:
//    int findMin(vector<int>& nums) {
//        int left = 0;
//        int right = nums.size() - 1;
//        int x = nums[right];
//        while (left < right)
//        {
//            int mid = (left + right) / 2;
//            if (nums[mid] < x)
//            {
//                right = mid;
//            }
//            else
//            {
//                left = mid + 1;
//            }
//        }
//        return nums[left];
//    }
//};
//
//class Solution {
//public:
//    int takeAttendance(vector<int>& records) {
//        int n = records.size();
//        int left = 0;
//        int right = n - 1;
//        while (left < right)
//        {
//            int mid = (left + right) / 2;
//            if (records[mid] > mid)
//            {
//                right = mid;
//            }
//            else
//            {
//                left = mid + 1;
//            }
//        }
//        if (records[left] == left)
//        {
//            return left + 1;
//        }
//        return left;
//    }
//};

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size();
        int left = 0;
        int right = n - 1;
        int x = nums[right];
        while (left < right)
        {
            int mid = (left + right) / 2;
            if (nums[mid] == target)
            {
                return mid;
            }
            if (nums[mid] < x)
            {
                right = mid;
            }
            else
            {
                left = mid + 1;
            }
        }
        int end = left - 1;
        int begin = left;
        left = 0;
        right = n - 1;
        while (left <= end)
        {
            int mid = (left + end) / 2;
            if (nums[mid] > target)
            {
                end = mid - 1;
            }
            else if (nums[mid] < target)
            {
                left = mid + 1;
            }
            else
            {
                return mid;
            }
        }
        while (begin <= right)
        {
            int mid = (begin + right) / 2;
            if (nums[mid] > target)
            {
                right = mid - 1;
            }
            else if (nums[mid] < target)
            {
                begin = mid + 1;
            }
            else
            {
                return mid;
            }
        }
        return -1;
    }
};

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int n1 = matrix.size();
        int n2 = matrix[0].size();
        int left = 0;
        int right = n1 - 1;
        while (left < right)
        {
            int mid = (left + right) >> 1;
            if (matrix[mid][n2 - 1] == target)
            {
                return true;
            }
            if (matrix[mid][n2 - 1] > target)
            {
                right = mid;
            }
            else
            {
                left = mid + 1;
            }
        }
        if (matrix[left][n2 - 1] == target)
        {
            return true;
        }
        int n3 = left;
        left = 0;
        right = n2 - 1;
        while (left <= right)
        {
            int mid = (left + right) >> 1;
            if (matrix[n3][mid] == target)
            {
                return true;
            }
            if (matrix[n3][mid] > target)
            {
                right = mid - 1;
            }
            else
            {
                left = mid + 1;
            }
        }
        return false;
    }
};

int main()
{
    Solution s;
    vector<int> v = { 4,5,6,7,0,1,2 };
    cout << s.search(v, 2) << endl;
    return 0;
}